Problema de cobertura de conjuntos

O problema de cobertura de conjuntos é uma questão clássica em combinatória, ciência da computação, pesquisa operacional e teoria da complexidade computacional . É um dos 21 problemas NP-completos de Karp mostrado ser NP-completo em 1972.

É um problema "cujo estudo levou ao desenvolvimento de técnicas fundamentais para todo o campo" dos algoritmos de aproximação .^[1]

Dado um conjunto universo ${\displaystyle \{1,2,...,n\}}$ e uma coleção ${\displaystyle S}$ de ${\displaystyle m}$ conjuntos cuja união é igual ao conjunto universo, o problema de cobertura de conjunto é identificar a menor sub-coleção de ${\displaystyle S}$ cuja união é igual ao conjunto universo. Por exemplo, considere o conjunto universo ${\displaystyle U=\{1,2,3,4,5\}}$ e a coleção de conjuntos ${\displaystyle S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}}$ . Claramente a união de ${\displaystyle S}$ é ${\displaystyle U}$ . No entanto, podemos cobrir todos os elementos com o mínimo número de conjuntos a seguir : ${\displaystyle \{\{1,2,3\},\{4,5\}\}}$ .

Mais formalmente, dado um conjunto universo ${\displaystyle U}$ e uma família ${\displaystyle S}$ de subconjuntos de ${\displaystyle U}$, uma capa é uma subfamília ${\displaystyle C\subseteq S}$ de conjuntos cuja união é ${\displaystyle U}$ . No conjunto que cumpre o problema de decisão, a entrada é um par ${\displaystyle (U,S)}$ e um inteiro ${\displaystyle k}$ ; a questão é se há uma cobertura de conjuntos de tamanho ${\displaystyle k}$ ou menos. No conjunto que cumpre o problema de otimização, a entrada é um par ${\displaystyle (U,S)}$, e a tarefa é encontrar uma cobertura de conjuntos que use o menor número de conjuntos.

A versão de decisão da cobertura do conjunto é NP-completa, e a versão de otimização / busca da cobertura do conjunto é NP-difícil . ^[2]

Se cada conjunto tiver um custo atribuído, ele se tornará um problema de cobertura de conjuntos ponderado .